tags:
  - DSA

SA. Insertion Sort

冒泡排序的核心是比较并交换，而插入排序的核心是插入。通过不断地将未排序的元素插入到已排序部分的适当位置，从而逐步构建一个有序的数组。相比冒泡排序，插入排序通过避免多余的交换操作，让排序一步到位，相当于打扑克牌时排序扑克。

插入排序的实现如下：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

分析插入排序的时空间复杂度：

最坏情况：
也就是数组完全逆序，每个元素都需要向前比较、移动并插入。它总的比较次数将是：即最差的比较时间复杂度为。这并不是插入排序的优点，它的优点是即便是最坏情况，它的插入（交换）的时间复杂度也最多为。
最好情况：
如果数组完全顺序，那么每个元素只需与前一个元素比较一次即可确认位置，无需进一步比较。因此，总比较次数为。时间复杂度为。不需要任何交换操作。